# from ..week.LeetCoder import *
from typing import *
from math import gcd


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        cnt1 = 0
        n = len(nums)
        cost = dict()
        s1 = 10000
        for v in nums:
            if v == 1:
                cnt1 += 1
            tmp = {}
            for c, cnt in cost.items():
                g = gcd(v, c)
                tmp[g] = cnt + 1
                if g == 1:
                    s1 = min(s1, tmp[g])
            tmp[v] = 0
            cost = tmp

        return n - cnt1 + max(s1 - 1, 0) if s1 != 10000 else -1


s = Solution()
print(s.minOperations([6, 10, 15]))
print(s.minOperations([10, 5, 10, 30, 70, 4, 2, 6, 8, 4]))


class Solution:
    def minOperations(self, nums: List[int]) -> int:
        if 1 in nums:
            return len(nums) - nums.count(1)
        res = -1
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                d = nums[j]
                for k in range(i, j):
                    d = gcd(d, nums[k])
                if d == 1:
                    if res == -1 or j - i + 1 < res:
                        res = j - i + 1
        if res == -1:
            return -1
        return len(nums) + res - 2
